\input{euler.tex}

\begin{document}

\problem[207]{Integer Partition Equations}

For certain positive integers $k$, there exists a real number $t \ge 0$ such that 
\[
4^t = 2^t + k, 
\]
and $(4^t, 2^t, k)$ are all integers. We call $(4^t, 2^t, k)$ a \emph{partition}. The first two partitions are $(4^1, 2^1, 2)$ and $(4^{1.5849625 \ldots}, 2^{1.5849625 \ldots}, 6)$.

A partition where $t$ is also an integer is called a \emph{perfect partition}.

Given $m \ge 2$, let $P(m)$ be the proportion of perfect partitions within all the partitions such that $1 \le k \le m$.

Find the smallest $m$ for which $P(m) < 1/12345$.

%[\emph{Note: this problem is slightly modified from the original problem by including the case $k = 1$. The solution is unchanged.}]

\solution

Let $n = 2^t$ be an integer. We can rewrite the partition definition as
\[
k = 4^t - 2^t = n^2 - n.
\]
Since $k$ is required to be positive, we require $n \ge 2$. Thus, any partition $(4^t, 2^t, k)$ is uniquely mapped to $(n^2, n, n^2-n)$, and vice versa. In addition, $k$ is monotonic in $n$.

Let $Q(n)$ be the proportion of perfect partitions among all partitions such that $2^t \le n$. There are $(n - 1)$ such partitions in total. A perfect partition requires $t$ to be an integer, so there are $\lfloor \log_2 n \rfloor$ perfect partitions. Therefore,
\[
Q(n) = \frac{\lfloor \log_2 n \rfloor }{n - 1} .
\]

To find the smallest $n$ such that 
\begin{equation}
Q(n) = \frac{\lfloor \log_2 n \rfloor }{n - 1} < \frac{1}{q} , \label{eq:207.1}
\end{equation}
rewrite it in the equivalent form
\begin{equation}
n > q \cdot \lfloor \log_2 n \rfloor + 1 . \label{eq:207.2}
\end{equation}
Hence we can start with $n_0 = 2$ and apply the following iterative formula
\begin{equation}
n_i =  q \cdot \lfloor \log_2 n_{i-1} \rfloor + 2 ,  \label{eq:207.3}
\end{equation}
until $n_i$ satisfies \eqref{eq:207.1}. Since $\log_2 n$ grows much more slowly than $n$, the algorithm converges quickly. It is also easy to see that the $n$ found this way is indeed the smallest $n$ that satisfies \eqref{eq:207.1}.

It then follows that $m = n^2 - n$ is the smallest $m$ such that $P(m) < 1/q$.

\answer

44043947822

\complexity

Time complexity: $\BigO(\ln q)$.

Space complexity: $\BigO(1)$.

\end{document} 